/**
 * @(#)LC941有效的山脉数组.java, 9月 28, 2021.
 * <p>
 * Copyright 2021 fenbi.com. All rights reserved.
 * FENBI.COM PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package com.wxweven.algorithm.array;

/**
 * @author wxweven
 */
public class LC941有效的山脉数组 {
    /*
     * 给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。
     *
     * 让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：
     *
     * arr.length >= 3
     * 在 0 < i < arr.length - 1 条件下，存在 i 使得：
     * arr[0] < arr[1] < ... arr[i-1] < arr[i]
     * arr[i] > arr[i+1] > ... > arr[arr.length - 1]
     *  
     * 示例 1：
     *
     * 输入：arr = [2,1]
     * 输出：false
     * 示例 2：
     *
     * 输入：arr = [3,5,5]
     * 输出：false
     * 示例 3：
     *
     * 输入：arr = [0,3,2,1]
     * 输出：true
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/valid-mountain-array
     */

    public boolean validMountainArray(int[] arr) {
        if (arr == null || arr.length < 3) {
            return false;
        }

        int len = arr.length;
        int left = 0;
        int right = len - 1;

        while (left + 1 < len && arr[left] < arr[left + 1]) {
            left++;
        }

        while (right - 1 >= 0 && arr[right - 1] > arr[right]) {
            right--;
        }

        // left 和 right 相等就是找到山峰，但是得排除几种特殊情况：
        // 1. 数组单调递增，这样left一直加，跟right相等，即right没动；
        // 2. 数组单调递减，这样right一直减，跟left相等，即left没动；
        // 所以排除的情况是：left 没动和 right没动
        return left == right
                && left != 0 // 排除 left 没动
                && right != len - 1; // 排除 right 没动
    }

}